package com.kaizen.leet234;

/**
 *
 * @author kaizen
 * @date 2020/6/7 11:28
 */
public class Solution {

    /**
     *
     * 执行用时 :
     * 1 ms
     * , 在所有 Java 提交中击败了
     * 99.76%
     * 的用户
     * 内存消耗 :
     * 42.3 MB
     * , 在所有 Java 提交中击败了
     * 10.81%
     * 的用户
     *作者：nuan
     *链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/wo-de-kuai-man-zhi-zhen-du-cong-tou-kai-shi-gan-ju/
     *来源：力扣（LeetCode）
     *著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}
